package day_2023_7_to_10;

import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2023/08/05 22:45
 **/
public class Day_8_5 {
    class Solution {
        public int movingCount(int m, int n, int k) {
            boolean[][] mat = new boolean[m][n];
            return movingCountHelper(mat, m, n, 0, 0, k);
        }
        public int movingCountHelper(boolean[][] mat, int m, int n, int i, int j, int k) {
            if(i >= m || j >= n || mat[i][j] || (i%10 + i/10 + j%10 + j/10) > k) return 0;
            mat[i][j] = true;
            return 1 + movingCountHelper(mat, m, n, i+1, j, k) + movingCountHelper(mat, m, n, i, j+1, k);
        }
    }
    class Solution2 {
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            pathSumHelper(root, target, new LinkedList<>());
            return res;
        }
        public void pathSumHelper(TreeNode root, int target, List<Integer> ret) {
            if(root == null) return;
            target -= root.val;
            if(root.left == null && root.right == null) {
                if(target == 0) {
                    ret.add(root.val);
                    res.add(new LinkedList<>(ret));
                    ret.remove(ret.size()-1);
                }else return;
            }
            ret.add(root.val);
            pathSumHelper(root.left, target, ret);
            pathSumHelper(root.right, target, ret);
            ret.remove(ret.size()-1);
        }
    }

}